package test;

/**
 * @author Marioszk
 * 树的最大深度
 * BFS 广度优先遍历算法
 */
public class TreeMaxDepth_树的最大深度 {
    private static class Node {
        /**
         * 节点值
         */
        public int value;
        /**
         * 左节点
         */
        public Node left;
        /**
         * 右节点
         */
        public Node right;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * leetcode 104: 求树的最大深度
     *
     * @param node
     * @return
     */
    public static int getMaxDepth(Node node) {
        if (node == null) {
            return 0;
        }
        int leftDepth = getMaxDepth(node.left) + 1;
        int rightDepth = getMaxDepth(node.right) + 1;
        return Math.max(leftDepth, rightDepth);
    }

    /**
     * leetcode 111: 求树的最小深度
     *
     * @param node
     * @return
     */
    public static int getMinDepth(Node node) {
        if (node == null) {
            return 0;
        }

        if (node.left == null) {
            return 1 + getMinDepth(node.right);
        }

        if (node.right == null) {
            return 1 + getMinDepth(node.left);
        }

        int leftDepth = getMinDepth(node.left);
        int rightDepth = getMinDepth(node.right);
        return 1 + Math.min(leftDepth, rightDepth);
    }
}
